Sellers of large or complex assets need to consider how to divide and package the assets. Packaging decisions are potentially important whenever there are value dependencies among items in the sense that a bidder's value for a package is different from the sum of the values of the separate parts. For example, a wireless telephone company purchasing radio spectrum rights may realize synergies from obtaining geographically-adjacent licenses. A flower wholesaler in Holland may incur fixed costs for shipping, handling and overhead that make single lot transactions unprofitable. Since flowers are highly perishable, it may also want to limit its purchases to what it can quickly resell. In real estate sales, some potential buyers may be interested in a whole complex of properties while others simply want space for individual homes or businesses. All of these are examples of value dependencies and all can make buyers interested in the way items are packaged for sale.
In practice, sellers accommodate these packaging preferences in a variety of ways. For example, government-run spectrum auctions are invariably preceded by political processes in which potential buyers press their cases about such matters as the allowed uses of the spectrum and the scope of the licenses in terms of bandwidth, band composition, and geographic coverage. In private auctions of relatively homogeneous goods, winning bidders may be allowed to purchase as many similar lots as they like at the winning price before bids are taken for the remaining lots. In the real estate example, bids might be taken both for a whole complex and for its individual properties, and the two constellations of prices compared.
In the last few years, there has been growing interest in auction processes that allow bidders much greater freedom to name the packages on which they bid during the auction. Processes like that described for the real estate example, which determine the packaging, pricing and allocation decisions, can be called “package auctions” or “auctions with package bidding.” Typically, bidders in these auctions describe the packages that they wish to acquire and make bids for the named packages.
The package auction that is best known among economists is a sealed-bid auction. The items for sale are taken to be M exogenously given “goods” and each bidder submits bids on every one of the 2M−1 possible packages. With distinct goods, such an auction can become impractically complicated for the bidders when M is still a single digit number. Although there are special cases in which the sealed-bid auction works well with larger numbers of goods, the sheer complexity of the general problem with many distinct kinds of goods has led auction designers to investigate alternative, dynamic auctions, which are often easier for bidders to comprehend and manage.
There is another practical issue that recommends package auctions. It is that the current alternatives to package bidding adopted by spectrum and electricity regulators have significant drawbacks of their own that package auctions can avoid. When the items for sale are substitutes, large bidders in multi-unit auctions find it in their interest to withhold some of their demand, in order to avoid driving up prices or to divide the spoils with other large bidders. Such “demand reduction” leads to inefficiency of the final allocation.
The present invention primarily concerns dynamic auctions with package bidding. These are multi-item auctions in which bidders may bid on packages (as well as single items) and may improve their bids or add new packages during the course of the auction. The eventual winning bids are traditionally the ones that optimize the total price of the goods.
There are several goals that arise repeatedly in the design of package auctions. The first is computational: there must be some sense in which, if bidders bid straightforwardly and bid evaluation costs are trivial, the auction outcome will be good ones according to revenue and efficiency criteria. Second, because package bidding is often very complex, simplicity is an important objective of auction design. Dynamic designs are sometimes favored over similar one-shot designs, for their relative comprehensibility and because they eliminate the need for bidders to evaluate closely every possible package. Third, the incentives for individuals or coalitions to deviate from straightforward bidding should be small or zero. Finally, the incentives for individuals and coalitions to deviate from efficient pre-auction investment decisions should also be small or zero.
Various systems and methods in the art facilitate the operation of computer-implemented auctions. The implementation of auctions on computers holds numerous advantages over the earlier art. It facilitates the simultaneous auctioning—in a single, combined auction process—of a plurality of items that are related, for example, in the sense that bidders may value the items as substitutes or complements. It permits a dynamic bidding process for such a plurality of items, in which bidders in diverse locations across the continent or the globe are able to actively participate and to receive feedback in real time about their opponents' bids. It enables the practical introduction of auctions with package bidding. And in accomplishing the above, it encourages bidders to bid aggressively and straightforwardly for the packages they want, incorporating all available information, and resulting in items being allocated to the bidders who value them the most, while also ensuring a competitive price for the seller or sellers.
However, there are various important limitations to the systems and methods for computer-implemented auctions in the art. This poses a technical problem to be addressed by the present invention. In particular:                Systems and methods for auctions of dissimilar items generally lack effective mechanisms whereby bidders can have computers place bids on their behalf.        Many auction systems and methods in the art are susceptible to tacit collusion among bidders, much to the detriment of allocative efficiency and revenue maximization.        Many auction systems and methods in the art lack effective “activity rules” that would constrain bidders to bid seriously in the early stages of the auction.        Systems and methods for auctions with package bidding generally require lengthy computations which limit the scalability of the process to auctions of a large number of items.        Systems and methods for dynamic auctions with package bidding generally accept only bids comprising packages of items and associated prices for the package.        
The present invention is an improved system and method for a computer-implemented auction, particularly for a computer-implemented dynamic auction with package bidding. Various preferred embodiments of the present invention resolve a number of important limitations to the systems and methods for computer-implemented auctions in the art. Thus, the present invention offers the further technical effect of improving computer-implemented auctions, making them operate more efficiently in terms of the ability of bidders to readily participate and to express their needs and preferences, more efficiently in terms of the allocation of items determined by the computer, and more quickly in terms of computer time. In particular:                Some preferred embodiments provide effective “proxy agents” for auctions of a plurality of dissimilar items, whereby bidders can have computers place bids on their behalf.        Some preferred embodiments introduce mandatory proxy bidding for auctions, requiring bids to be intermediated by proxy agents and limiting changes of bid information, thereby curtailing possibilities for tacit collusion among bidders and also accelerating the auction process.        Some preferred embodiments introduce “bid improvement rules,” “revealed-preference-based bidding constraints,” and “price-based bidding constraints” that help to constrain bidders to bid seriously in the early stages of the auction.        Some preferred embodiments provide limitations on the number of bids that need to be considered at each calculation step, reducing the computation time for determining provisional winners and thereby improving scalability to large numbers of items.        Some preferred embodiments include augmented dynamic package-bidding auction processes in which other information (besides prices and quantities) may be explicitly included in bids, bidder-specific attributes may be implicitly included in bids, and both may be included in the auction computer's objective function and selection constraints.        
The present invention is useful for “reverse auctions” conducted by or for buyers to acquire various kinds of items or resources, “standard auctions” conducted by sellers in which items are offered for sale, and “exchanges” in which both buyers and sellers place bids. Although terms such as “items or quantities demanded” (by a bidder) and “demand curve” (of a bidder) are used to describe the present invention, the terms “items or quantities offered” (by a bidder) and “supply curve” (of a bidder) are equally applicable. In some cases, this is made explicit by the use of both terms, or by the use of the terms “items or quantities transacted” (by a bidder) and “transaction curve” (of a bidder). The term “items or quantities transacted” includes both “items or quantities demanded” and “items or quantities offered”. The term “bid” includes both offers to sell and offers to buy. The term “transaction curve” includes both “demand curve” and “supply curve”. Moreover, any references to “items or quantities being offered” includes both “items or quantities being sold” by the auctioneer, in the case this is a standard auction for selling items, as well as “items or quantities being bought or procured” by the auctioneer, in the case this is a reverse auction for buying items or procuring items.
Moreover, while standard auctions to sell typically involve ascending prices, the present invention may utilize prices that ascend and/or descend.
Throughout this document, the terms “objects”, “items”, “units” and “goods” are used essentially interchangeably. The inventive system and method may be used both for tangible objects, such as real or personal property, and intangible items, such as telecommunications licenses or electric power. The inventive system and method may be used in auctions where the auctioneer is a seller, buyer or broker, the bidders are buyers, sellers or brokers, and for auction-like activities which cannot be interpreted as selling or buying. The inventive system and method may be used for items including, but not restricted to, the following: public-sector bonds, bills, notes, stocks, and other securities or derivatives; private-sector bonds, bills, notes, stocks, and other securities or derivatives; communication licenses and spectrum rights; clearing, relocation or other rights concerning encumbrances of spectrum licenses; electric power and other commodity items; rights for terminal, entry, exit or transmission capacities or other rights in gas pipeline systems; airport landing rights; emission allowances and pollution permits; and other goods, services, objects, items or other property, tangible or intangible. It may also be used for option contracts on any of the above. It may be used in initial public offerings, secondary offerings, and in secondary or resale markets.
The network used, if any, can be any system capable of providing the necessary communication to/from a Bidding Information Processor (BIP), a Bidding Terminal (BT), and an Auctioneer's Terminal (AT). The network may be a local or wide area network such as, for example, Ethernet, token ring, the Internet, the World Wide Web, the information superhighway, an intranet or a virtual private network, or alternatively a telephone system, either private or public, a facsimile system, an electronic mail system, or a wireless communications system, or combinations of the foregoing.
The following patents and published applications are related to the present invention:    Ausubel, Lawrence M., U.S. Pat. No. 5,905,975, May 1999.    Ausubel, Lawrence M., U.S. Pat. No. 6,021,398, February 2000.    Ausubel, Lawrence M., U.S. Pat. No. 6,026,383, February 2000.    Ausubel, Lawrence M., Application No. 00304195.1 at the European Patent Office, May 2000.
The following other references are related to the present invention:    Arrow, Kenneth, H. D. Bloch and Leonid Hurwicz (1959), “On the Stability of Competitive Equilibrium, II,” Econometrica 27: 82-109.    Ausubel, Lawrence M. (1997a), “An Efficient Ascending-Bid Auction for Multiple Objects,” Working Paper 97-06, University of Maryland, http://www.ausubel.com/auction-papers/97wp-efficient-ascending-auction.pdf.    Ausubel, Lawrence M. (1997b), “On Generalizing the English Auction,” working paper, http://www.ausubel.com/auction-papers/97wp-generalizing-the-english-auction.pdf.    Ausubel, Lawrence M. (2000), “An Efficient Dynamic Auction for Heterogeneous Commodities,” Working Paper, University of Maryland, www.ausubel.com.    Ausubel, Lawrence M. and Peter Cramton (1996), “Demand Reduction and Inefficiency in Multi-Unit Auctions,” Working Paper No. 96-07, http://www.cramton.umd.edu/papers1995-1999/98wp-demand-reduction.pdf    Ausubel, Lawrence M., Peter Cramton, R. Preston McAfee, and John McMillan (1997), “Synergies in Wireless Telephony: Evidence from the Broadband PCS Auctions,” Journal of Economics and Management Strategy, 6:3, 497-527.    Banks, Jeffrey S., John O. Ledyard and David P. Porter, “Allocating Uncertain and Unresponsive Resources: An Experimental Approach,” Rand Journal of Economics, 20: 1-25.    Bernheim, B. Douglas and Michael Whinston (1986), “Menu Auctions, Resource Allocation and Economic Influence,” Quarterly Journal of Economics, 101: 1-31.    Bikhchandani, Sushil and Joseph M. Ostroy (1999), “The Package Assignment Problem,” working paper, UCLA.    Bulow, Jeremy, Ming Huang and Paul Klemperer (1999), “Toeholds and Takeovers,” Journal of Political Economy, 107(3): 427-454.    Cassady, Ralph (1967). Auctions and Auctioneering. Berkeley: University of California Press.    Charles River Associates and Market Design Inc. (1997), “Package Bidding for Spectrum Licenses,” Report to the Federal Communications Commission. Available at http://www.fcc.gov/wtb/auctions/combin/cr—2.pdf.    Che, Yeon-Koo and Ian Gale (1998), “Standard Auctions with Financially Constrained Bidders,” Review of Economic Studies, 65: 1-21.    Clarke, E. H. (1971), “Multipart Pricing of Public Goods,” Public Choice, XI, 17-33.    Cybernomics (2000), “An Experimental Comparison of the Simultaneous Multiple Round Auction and the CRA Combinatorial Auction.” Report to the Federal Communications Commission. Available at http://www.fcc.gov/wtb/auctions/combin/98540191.pdf.    DasVarma, Gopal (2000a), “Standard Auctions with Identity-Dependent Externalities,” working paper, Duke University.    DasVarma, Gopal (2000b), “The Pareto Optimality of Disclosing Bidder Identities,” working paper, Duke University.    G. Demange, D. Gale and M. Sotomayer, “Multi-Item Auctions,” Journal of Political Economy, vol. 94, No. 4, 1986, pp. 863-872.    DeMartini, Christine, Anthony Kwasnica, John Ledyard, and David Porter (1999), “A New and Improved Design for Multi-Object Iterative Auctions,” Cal Tech working paper.    DeVries, Sven and Rakesh Vohra (2001), “Combinatorial Auctions: A Survey.” Working paper. Available at http://www-m9.ma.tum.de/˜devries/comb_auction_supplement/comauction.pdf.    Federal Commiunications Commission (1995), “Bidder Information Packet for FCC Auction Scheduled for Aug. 2, 1995.”    Federal Communications Commission (1995), “Bidder Information Packet for FCC Auction Scheduled for Dec. 11, 1995.”    Federal Communications Commission (2000), “Bidder Information Packet for FCC Auction No. 31.”    Groves, Theodore (1973), “Incentives in Teams,” Econometrica 61: 617-31.    Gul, Faruk and Ennio Stacchetti (1999), “Walrasian Equilibrium with Gross Substitutes,”Journal of Economic Theory, 87, 9-124.    F. Gul and E. Stachetti (2000), “English and Double Auctions with Differentiated Commodities”, Journal of Economic Theory, 92, 66-95.    Holmstrom, Bengt (1979), “Groves Schemes on Restricted Domains,” Econometrica 47: 1137-1144.    Jehiel, Philippe and Benny Moldovanu (2001), “The European UMTS/IMA-2000 License Auctions,” working paper.    Kelso, Alexander S. and Vincent P. Crawford (1982), “Job Matching, Coalition Formation, and Gross Substitutes,” Econometrica 50: 1483-1504.    Ledyard, John, David Porter and Antonio Rangel (1997), “Experiments Testing Multi-object Allocation Mechanisms,” Journal of Economics and Management Strategy, 6: 639-675.    R. P. McAfee and J. McMillan, “Auctions and Bidding,” Journal of Economic Literature, vol. 25, June 1987, pp. 699-738.    K. A. McCabe, S. J. Rassenti and V. L. Smith, “Testing Vickrey's and Other Simultaneous Multiple Unit Versions of the English Auction,” Research in Experimental Economics, vol. 4, Greenwich, Conn.: JAI Press, 1991, pp. 45-79.    McMillan, John (1994), “Selling Spectrum Rights,” Journal of Economics Perspectives, 8: 145-162.    Milgrom, Paul (1981), “Rational Expectations, Information Acquisition, and Competitive Bidding,” Econometrica, 49: 921-43.    F. M. Menezes, Four Essays on Auction Theory, University of Illinois doctoral dissertation, February 1993, pp. 1-97 and 143-152.    Milgrom, Paul (1996), “Auctioning the Radio Spectrum,” www.market-design.com.    Milgrom, Paul (2000). “Putting Auction Theory to Work: The Simultaneous Ascending Auction,” Journal of Political Economy, 108:2, 245-272.    Milgrom, Paul and John Roberts (1991), “Adaptive and Sophisticated Learning in Repeated Normal Form Games,” Games and Economic Behavior, 3: 82-100.    Milgrom, Paul and Ilya Segal (2000), “Envelope Theorems for Arbitrary Choice Sets,” forthcoming in Econometrica.     Milgrom, Paul and Robert Weber (1982), “A Theory of Auctions and Competitive Bidding,” Econometrica 50: 1089-1122.    Nisan, Noam (1999), “Bidding and Allocation in Combinatorial Auctions,” working paper, http://www.cs.huji.ac.il/˜noam/mkts.html.    Palfrey, Thomas (1983), “Bundling Decisions by a Multiproduct Monopolist with Incomplete Information,” Econometrica, 51: 463-483.    D. C. Parkes (1999), “iBundle: An Efficient Ascending Price Bundle Auction”, Proceedings ACM Conference on Electronic Commerce (EC-99), Denver, 148-157.    Plott, Charles (1997), “Laboratory Experimental Testbeds: Application to the PCS Auction,” Journal of Economics and Management Strategy, 6: 605-638.    Porter, David (1997), “The Effect of Bid Withdrawal in a Multi-Object Auction,” working paper, University of Arizona.    Rassenti, S. J., V. L. Smith, and R. L. Bulfin (1982), “A Combinatorial Auction Mechanism for Airport Time Slot Allocation,” Bell Journal of Economics XIII: 402-417.    Roth, Alvin E. and Elliott Peranson (1999), “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design,” American Economic Review, 89: 748-780.    Roth, Alvin E. and Marilda A. Oliveira Sotomayor (1990), Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge: Cambridge University Press.    M. H. Rothkopf, A. Pekec and R. M. Harstad (1998), “Computationally Manageable Combinatorial Auctions”, Management Science, Vol. 44, No. 8, 1131-1147.    Rothkopf, Michael, Thomas Teisberg and Edward Kahn (1990), “Why Are Vickrey Auctions Rare?” Journal of Political Economy, 98: 94-109.    Scarf, Herbert (1960), “Some Examples of Global Instability of the Competitive Equilibrium,” International Economic Review, 1: 157-172.    Sholtz & Associates, LLC, “ACE Market Operations Guide,” Jan. 3, 1996, pp. 1-5.    U.S. Department of the Treasury, U.S. Securities and Exchange Commission, and Board of Governors of the Federal Reserve System, Joint Report on the Government Securities Market, Washington, D.C.: U.S.G.P.O., January 1992.    Vickrey, William (1961), “Counterspeculation, Auctions and Competitive Sealed Tenders,” Journal of Finance, XVI, 8-37.    W. Vickrey, “Auctions and Bidding Games,” Recent Advances in Game Theory, Princeton: Princeton University Conference, 1962, pp. 15-29.    W. Vickrey, “Auctions, Markets, and Optimal Allocation,” Bidding and Auctioning for Procurement and Allocation, New York: New York University Press 1976, pp. 13-20.    R. J. Weber, “Multiple-Object Auctions,” Auctions, Bidding, and Contracting: Uses and Theory, New York: New York University Press, 1983, pp. 165-191.    Weber, Robert (1997), “Making More from Less: Strategic Demand Reduction in the FCC Spectrum Auctions,” Journal of Economics and Management Strategy, 6:529-548.    Williams, Steven (1999), “A Characterization of Efficient, Bayesian Incentive Compatible Mechanisms,” Economic Theory XIV: 155-180.    R. Wilson, “Auction of Shares,” Quarterly Journal of Economics, vol. 94, 1979, pp. 675-689.